package indi.gao.leetcode.swardToOffer;

/**
 * <p>Description:</p>
 * 找出数组中重复的数字。
 * <p>
 * <p>
 * 在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
 * <p>
 * 示例 1：
 * <p>
 * 输入：
 * [2, 3, 1, 0, 2, 5, 3]
 * 输出：2 或 3
 */
public class FindDuplicateNum {
    public static void main(String[] args) {
        int[] nums = {2, 3, 5, 4, 2, 4};
        System.out.println(new Solution1().findRepeatNumber(nums));
    }
}

/**
 * 我们可以构建这个一个特殊的哈希表，下标0~n-1依次对应数值0~n-1有没有出现过，
 * 如果数字x第一次出现，那么下标x 的位置的元素应该为该位置的相反值，标识这个数字x出现过，
 * 当我们下一次再遇到x，判断一下下标x的值是否<0，如果是的话表示之前已经访问过
 * ，我们就找到了这个重复的数 因为题意表明一定有重复的数字 所以如果在前面都没有返回的话
 * 说明重复的数字就是0 直接最后返回0就好了
 */
class Solution1 {
    public int findRepeatNumber(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] < 0 && nums[-nums[i]] < 0) {
                return -nums[i];
            } else if (nums[i] > 0 && nums[nums[i]] < 0) {
                return nums[i];
            } else {
                if (nums[i] < 0) {
                    nums[-nums[i]] = -nums[-nums[i]];
                } else {
                    nums[nums[i]] = -nums[nums[i]];
                }
            }
        }
        return 0;
    }

}